import java.util.*;

public class BinaryTree<E> {
    //孩子表示法
    static class Node<E> {
        E val;
        Node<E> left;
        Node<E> right;

        public Node(E val) {
            this.val = val;
        }
    }

    /**
     孩子双亲表示法
     static class Node<E>{
       E val;
     Node<E> left;//对应节点的左节点
     Node<E> right;//对应节点的右节点
     Node<E> parent;//对应节点的父节点

     public Node(E val){
        this.val = val
     }
    }
     */
    //根节点
    public Node root;

    public void creatTree() {
        Node<Character> A = new Node<>('A');
        Node<Character> B = new Node<>('B');
        Node<Character> C = new Node<>('C');
        Node<Character> D = new Node<>('D');
        Node<Character> E = new Node<>('E');
        Node<Character> F = new Node<>('F');
//        Node<Character> G = new Node<>('G');
//        Node<Character> H = new Node<>('H');

        root = A;
        A.left = B;
        B.left = D;
        A.right = C;
        C.left = E;
        C.right = F;
//        D.left = G;
//        G.right = H;
    }

    public Node root2;

    public void creatTree2() {
        Node<Character> A = new Node<>('A');
        Node<Character> B = new Node<>('B');
        Node<Character> C = new Node<>('C');
        Node<Character> D = new Node<>('D');
        Node<Character> E = new Node<>('E');
        Node<Character> F = new Node<>('F');
        Node<Character> G = new Node<>('G');
        Node<Character> H = new Node<>('H');

        root2 = A;
        A.left = B;
        B.left = D;
        A.right = C;
        C.left = E;
        C.right = F;
        D.left = G;
        G.right = H;
    }

    public Node root3;

    public void creatTree3() {

        Node<Character> A = new Node<>('A');
        Node<Character> B = new Node<>('B');
        Node<Character> C = new Node<>('B');
        root3 = A;
        A.left = B;
        A.right = C;
    }

    public Node root4;
    public Node subRoot;

    public void creatTree4() {
        Node<Character> A = new Node<>('A');
        Node<Character> B = new Node<>('B');
        Node<Character> C = new Node<>('B');
        Node<Character> D = new Node<>('C');
        Node<Character> E = new Node<>('C');
        Node<Character> F = new Node<>('D');
        Node<Character> G = new Node<>('D');
        root4 = A;
        subRoot = C;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = F;
        C.right = E;
        C.left = G;
    }

    public void createTree5() {
        Node<Character> A = new Node<>('1');
        Node<Character> B = new Node<>('2');
        Node<Character> C = new Node<>('3');
        Node<Character> D = new Node<>('4');
        Node<Character> E = new Node<>('5');
        Node<Character> F = new Node<>('6');
        Node<Character> G = new Node<>('7');
        root = A;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
    }
    public void createTree6() {
        Node<Character> A = new Node<>('1');
        Node<Character> B = new Node<>('2');
        Node<Character> C = new Node<>('3');
        Node<Character> D = new Node<>('4');
        Node<Character> E = new Node<>('5');
        root = A;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
    }
    //根据前序遍历和中序遍历创建树
    public Node buildTree(E[] preorder, E[] inorder) {
        int rootBegin = 0;//是 树的头节点
        int rootEnd = inorder.length - 1;//是树的尾节点
        //当end大于begin是说明左树创建好了，
        // begin大于end说明右树创建好了
        Node Root = buildTreeMain(preorder, inorder, rootBegin, rootEnd);
        return Root;

    }

    int preIndex = 0;

    private Node buildTreeMain(E[] preorder, E[] inorder,
                               int rootBegin, int rootEnd) {

        //这是rootEnd为-1 表示左树创建好了 || rootBegin > rootEnd 右树创建好了
        if (rootBegin > rootEnd) {
            return null;
        }

        //找到preorder的值 在rootBegin, rootEnd这个范围
        int inIndex = findVal(preorder, inorder,
                preIndex, rootBegin, rootEnd);//是 inorder的根节点
        //preIndex  用来遍历preorder

        Node Root = null;
        if (inIndex == -1) {
            return null;
        } else {
            Root = new Node(inorder[inIndex]);
            preIndex++;
        }

        //创建左树

        Root.left = buildTreeMain(preorder, inorder, rootBegin, inIndex - 1);

        //创建右树

        Root.right = buildTreeMain(preorder, inorder, inIndex + 1, rootEnd);

        return Root;
    }

    private int findVal(E[] preorder, E[] inorder, int preIndex, int rootBegin, int rootEnd) {
        for (int j = rootBegin; j <= rootEnd; j++) {
            if (preorder[preIndex] == inorder[j]) {
                return j;
            }
        }
        return -1;//没找到说明放回null
    }

    /**
     * 根据前序遍历的字符串去创建二叉树
     * i 用来遍历字符串
     */
    int i = 0;

    public Node creatByString(String s) {
        Node root = null;
        if (s.charAt(i) != '#') {
            root = new Node(s.charAt(i));
            i++;
            root.left = creatByString(s);
            root.right = creatByString(s);
        } else {//说明是'#'直接加一就好
            i++;
        }
        return root;
    }

    //获取节点数目
    static int count = 0;

    public int size1(Node root) {
        if (root == null) {
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }

    public int size(Node root) {
        if (root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    //获得树中间隔最长的俩个节点
    boolean flag_LR = true;//如果最后是左边的数最长为true 左为false
    int retHeight = 0;
    public int diameterOfBinaryTree(Node root) {
        getHeight2(root);
        return retHeight;
    }

    public int getHeight2(Node root) {
        if (root == null) {
            return 0;
        }
        int tmpL = getHeight2(root.left);
        int tmpR = getHeight2(root.right);
        if (tmpL + tmpR > retHeight) {
            retHeight = tmpL + tmpR;
        }
        return Math.max(tmpL, tmpR) + 1;
    }


    //查找数据是否再树中
    public boolean find(Node root,E val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return find(root.left,val) || find(root.right,val);
    }

    //叶子的个数
    static int countLeaf = 0;

    public int getLeafNodeCount(Node root) {

        if (root == null) {
            return 0;
        }
        getLeafNodeCount(root.left);//从左边找
        if (root.right == null && root.left == null) {//是叶子
            countLeaf++;
            return 0;
        }
        getLeafNodeCount(root.right);//从右边找
        if (root.right == null && root.left == null) {//是叶子
            countLeaf++;
            return 0;
        }
        return countLeaf;
    }

    //获取第k层叶子的数目 root所在的第1层
    static int levelNodeCount = 0;

    public int getLevelCount(Node root, int k) {
        if (root == null || k < 0) {
            return 0;
        }
        if (k == 1) {//初始root所在的那层是1
            return ++levelNodeCount;
        }
        int level = k - 1;
        getLevelCount(root.left, level);
        getLevelCount(root.right, level);
        return levelNodeCount;
    }

    //获取树的高度
    public int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }

    //获取最短叶子路径
    public int getMinHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.min(getMinHeight(root.left), getMinHeight(root.right)) + 1;
    }

    //判断俩棵树是否相同
    public Boolean isSameTree(Node p, Node q) {
        if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        if (p == null && q == null) {
            return true;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //判断一棵树知否子另一可树中存在
    public Boolean isSubtree(Node root, Node sub) {
        boolean end = false;
        //遍历
        if (root == null) {
            return false;
        }
        if (root.val == sub.val) {//判断是否相同
            end = isSameTree(root, sub);
        }
        return end || isSubtree(root.left, sub) || isSubtree(root.right, sub);
    }

    //翻转树
    public void revetTree(Node root) {
        if (root == null) {
            return;
        }
        //翻转
        Node tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        //遍历树
        revetTree(root.right);
        revetTree(root.left);
    }

    //是否是轴对称树
    public Boolean isAxisymmetric(Node root) {
        if (root == null) {
            return true;
        }
        return isAxisymmetricTree(root.left, root.right);
    }

    private Boolean isAxisymmetricTree(Node rootLeft, Node rootRight) {
        if (rootLeft == null && rootRight == null) {
            return true;
        }
        if ((rootLeft != null && rootRight == null) || (rootLeft == null && rootRight != null)) {
            return false;
        }
        //判断是否对称 相同继续玩下
        if (rootLeft.val != rootRight.val) {
            return false;
        }
        if (rootLeft.val != rootRight.val) {
            return false;
        }
        //向下遍历
        return isAxisymmetricTree(rootLeft.left, rootRight.right)
                && isAxisymmetricTree(rootLeft.right, rootRight.left);
    }

    //是否是平衡树
    //O(1)解法
    public Boolean isBalanced(Node root) {

        if (root == null) {
            return true;
        }
        return getHeight1(root) >= 0;
    }

    private int getHeight1(Node root) {
        if (root == null) {
            return 0;
        }
        int heightLeft = getHeight1(root.left);
        if (heightLeft < 0) {
            return -1;
        }
        int heightRight = getHeight1(root.right);
        if (heightRight < 0 || Math.abs(heightLeft - heightRight) > 1) {//说名有节点不是平很姐节点
            return -1;
        }
        return Math.max(heightLeft, heightRight) + 1;
    }

    //O(n^2)
    public Boolean isBalanced1(Node root) {
        if (root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //左右树都要是平衡的
        return (Math.abs(leftHeight - rightHeight) <= 1)
                && isBalanced1(root.left) && isBalanced1(root.right);
    }


    //元素查找
    public Node treeNOde_find(Node root, E val) {

        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        Node rightV = treeNOde_find(root.right, val);
        if (rightV != null) {
            return rightV;
        }
        Node leftV = treeNOde_find(root.left, val);
        if (leftV != null) {
            return leftV;
        }
        return null;
    }

    //给一个有序数组转换为平衡二叉树 每次都是分一半这样就能包装俩边的高度不会超过2是平衡的
    public Node balanceBST(Node root) {
        //中序遍历得到一个有序的链表
        List<Integer> list = new LinkedList<>();
        inOrderList(list, root);
        root = createTree(list,  0, list.size() - 1);
        return root;
    }

    private Node createTree(List<Integer> list, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (end + start) >> 1;

        Node root = new Node(list.get(mid));//建立新节点

        root.left = createTree(list, start, mid - 1);//向左递归创建新节点
        root.right = createTree(list,mid + 1, end);//向右递归创建新节点

        return root;
    }

    private void inOrderList(List list, Node root) {
        if (root != null) {
            inOrderList(list, root.left);
            list.add(root.val);
            inOrderList(list, root.right);
        }
    }


    //找到俩个节点的最近的祖先 节点一定存在
    public Node lowestCommonAncestor(Node root, Node p, Node q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        Node leftNode = lowestCommonAncestor(root.left, p, q);
        Node rightNode = lowestCommonAncestor(root.right, p, q);
        //走到这里要么是没找到要么是找到了 放回的是找到了的节点
        if (leftNode != null && rightNode != null) {
            return root;
        } else if (leftNode != null && rightNode == null) {//找到了左边的
            return leftNode;
        } else {
            return rightNode;
        }
    }

    //将二叉树变为双向链表
    Node prev;
    Node head;

    public Node Convert(Node pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        swap(pRootOfTree);
        return head;
    }

    private void swap(Node root) {//root是要交换的根节点
        if (root == null) {
            return;
        }
        swap(root.left);
        //交换
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        if (prev == null) {//记录下头节点
            head = root;
        }
        prev = root;

        swap(root.right);
    }

    //以字符串方式输出树
    public String tree2str(Node root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strMain(root, stringBuilder);
        return stringBuilder.toString();
    }

    private void tree2strMain(Node node, StringBuilder s) {
        if (node == null) {
            return;
        }
        s.append(node.val);
        //递归左边 加上括号
        if (node.left != null) {
            s.append("(");
            tree2strMain(node.left, s);
            s.append(")");
        } else {//左边递归完了
            if (node.right == null) {
                return;
            } else {
                s.append("()");
            }
        }
        //递归右边
        if (root.right != null) {
            s.append("(");
            tree2strMain(node.right, s);
            s.append(")");
        } else {
            return;
        }
    }

    //前序遍历
    public void preOder(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOder(root.left);//走到左节点
        preOder(root.right);//走到有右节点
    }

    //中序遍历
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(Node root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //层序遍历
    public void levelOrder(Node root) {

        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    //会将空节点记为null
    public List<List<String>> levelOrder_null(Node root) {
        List<List<String>> arr = new LinkedList();
        if (root == null) {
            return arr;
        } else {
            Queue<Node> queue = new LinkedList();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int size = queue.size();

                LinkedList tmpL;
                for (tmpL = new LinkedList(); size != 0; --size) {
                    Node tmp = (Node) queue.poll();
                    if (tmp != null) {
                        tmpL.add("" + tmp.val);
                        queue.offer(tmp.left);
                        queue.offer(tmp.right);
                    } else {
                        tmpL.add("null");
                    }
                }

                arr.add(tmpL);
            }

            return arr;
        }
    }

    public List<List<Integer>> levelOrder1(Node root) {
        List<List<Integer>> arr = new LinkedList();
        if (root == null) {
            return arr;
        }
        Queue<Node> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmpL = new LinkedList<>();
            while (size != 0) {
                Node tmp = queue.poll();
                tmpL.add((Integer) tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
            arr.add(tmpL);
        }
//        Collections.reverse(arr);//从下到上打印
        return arr;
    }


    //非递归遍历
    public void preOrderNor(Node root) {

        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.add(cur);
                cur = cur.left;
            }
            //回退到上一个右节点
            Node tmp = stack.pop();
            cur = tmp.right;
        }
    }

    public void inOrderNor(Node root) {

        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.add(cur);
                cur = cur.left;
            }
            //回退到上一个右节点
            Node tmp = stack.pop();//得到的是中间节点，只不过有些是俩边都为null
            System.out.print(tmp.val + " ");
            cur = tmp.right;
        }
    }

    public void postOrderNor(Node root) {
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        Node prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.add(cur);
                cur = cur.left;
            }
            //回退到上一个右节点
            Node tmp = stack.peek();//得到的是中间节点，只不过有些是俩边都为null
            if (tmp.right == null || tmp.right == prev) {//说明右边的这个已经被打印了
                System.out.print(tmp.val + " ");
                stack.pop();
                prev = tmp;//记录被打印了的节点
            } else {
                cur = tmp.right;
            }
        }
    }
}

class text {
    public static void main(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.createTree6();
        System.out.println(hh.diameterOfBinaryTree(hh.root));
//        System.out.println(hh.getHeight2(hh.root));
//        System.out.println(hh.getHeight(hh.root));
//        System.out.println(hh.getMinHeight(hh.root));
//        System.out.println(hh.getHeight(hh.root));
    }
    public static void mai21n(String[] args) {
        //非递归
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.creatTree2();
        hh.preOder(hh.root2);
        System.out.println();
        hh.preOrderNor(hh.root2);
        System.out.println();

        hh.inOrder(hh.root2);
        System.out.println();
        hh.inOrderNor(hh.root2);
        System.out.println();

        hh.postOrder(hh.root2);
        System.out.println();
        hh.postOrderNor(hh.root2);
    }

    public static void main4(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.createTree5();
        hh.preOder(hh.root);
        System.out.println();
        hh.inOrder(hh.root);
        System.out.println();
        hh.postOrder(hh.root);
        System.out.println(hh.find(hh.root, '9'));
    }

    public static void main11(String[] args) {
//        Scanner in = new Scanner(System.in);
//        in.hasNextLine();
        BinaryTree<Character> hh = new BinaryTree<>();
        Character[] preorder = {'E', 'F', 'H', 'I', 'G', 'J', 'K'};
        Character[] inorder = {'H', 'F', 'I', 'E', 'J', 'K', 'G'};
        BinaryTree.Node hhh = hh.buildTree(preorder, inorder);
        hh.preOder(hhh);
        System.out.println();
        hh.inOrder(hhh);
        System.out.println();
        hh.postOrder(hhh);
        System.out.println();
        System.out.println(Arrays.toString(new List[]{hh.levelOrder_null(hhh)}));
    }

    public static void main6(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        BinaryTree.Node hhh = hh.creatByString("abc##de#g##f###");
        hh.inOrder(hhh);
    }

    public static void main5(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.creatTree();
        hh.levelOrder(hh.root);
        hh.creatTree4();
//        System.out.println(hh.isSubtree(hh.root4,hh.subRoot));
        System.out.println(hh.isAxisymmetric(hh.root4));
    }

    public static void main3(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.creatTree3();
        System.out.println(hh.isAxisymmetric(hh.root3));
    }

    public static void main2(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.creatTree();
        hh.creatTree2();
        System.out.println(hh.isSameTree(hh.root, hh.root2));
        System.out.println(hh.isSubtree(hh.root, hh.root2));
        hh.preOder(hh.root);
        System.out.println();
        hh.revetTree(hh.root);
        hh.preOder(hh.root);

    }

    public static void main1(String[] args) {
        BinaryTree<Character> hh = new BinaryTree<>();
        hh.creatTree();
        System.out.println("前序遍历");
        hh.preOder(hh.root);//前序遍历
        System.out.println("\n后序遍历");
        hh.inOrder(hh.root);//中序遍历
        System.out.println("\n后序遍历");
        hh.postOrder(hh.root);//后序遍历
        System.out.println("\nfind");
        for (char i = 'A'; i <= 'F'; i++) {
            System.out.print(hh.treeNOde_find(hh.root, i).val + " ");
        }
        System.out.println("\n节点总数");
        System.out.println(hh.size(hh.root));
        System.out.println("叶子总数");
        System.out.println(hh.getLeafNodeCount(hh.root));

        System.out.println("第k层的节点总数");
        System.out.println(hh.getLevelCount(hh.root, 3));
        System.out.println("树的深度");
        System.out.println(hh.getHeight(hh.root
        ));
    }
}
